package LearnAlgorithm.c_递归and查找排序;

import java.util.HashMap;

import com.sun.org.apache.bcel.internal.generic.RETURN;

public class o乱序数组查找第k小数 {
	public static void main(String[] args) {
		int[] arr = new int[] {1,6,3,4,5};//{1,3,4,5,6}
//		int[] arr = new int[] {1,2,3,4,5};
		
		int k = 2;
		int target = selectK(arr, 0, arr.length - 1, k);
		System.out.println(target);//输出3
		
		
		int target2 = selectKByindex(arr, 0, arr.length-1, k);
		System.out.println(target2);//输出3
	}
	
	public static int selectKByindex(int[] arr, int p, int r, int k) {
		return selectKIndex(arr, p, r, k - 1);
	}
	
	public static int selectKIndex(int[] arr, int p, int r, int k) {//这种直接把“第几小”转化成“索引是第几”的思想可行，但是要考虑边界值，写起来比老师讲的要麻烦一些
		if (p <= r) {
			int q = partition(arr, p, r);
			if (q == 0 && q != k) {//考虑两种边界值
				if (q + 1 == k) {
					return arr[q + 1];
				} else {
					return -1;
				}
			} else if (q == r - 1 && q != k) {//考虑两种边界值
				if (r == k) {
					return arr[r];
				} else {
					return -1;
				}
			}
			if (q == k) {//考虑其他数值情况
				return arr[q];
			} else if (k < q) {
				return selectKIndex(arr, p, q - 1, k);
			} else {
				return selectKIndex(arr, q + 1, r, k);
			}
		} else {
			return -1;
		}
	}
	
	public static int selectK(int[] arr, int p, int r, int k) {
		if (p <= r) {
			int q = partition(arr, p, r);
			int locationOfK = q - p + 1;
			if (locationOfK == k) {
				return arr[q];
			} else if (locationOfK > k) {
				return selectK(arr, p, q - 1, k);
			} else {
				return selectK(arr, q + 1, r, k - locationOfK);
				/*
				 * 这里k - locationOfK是把中值索引右边的所有元素视为新的数组()
				 * 新的数组中第(k - locationOfK)小元素就是原数组中第(k)小元素
				 * 1 4 3 4 5 原数组
				 * 中值3；中值索引2；locationOfK = 3；
				 * 设k = 4
				 * 那么新数组为 4 5
				 * 新数组的 第1小元素就是原数组的第4小元素
				 * 1 = k - locationOfK
				 * 4 = k 
				 */
			}
		} else {
			return -1;
		}
	}
	
	public static int partition(int[] arr, int p, int r) {
		int midIndex = getMedian(arr, p, r);
		int pivot = arr[midIndex];
		while (p <= r) {
			while (p <= r && arr[p] <= pivot) {
				p++;
			}
			while (p <= r && arr[r] > pivot) {
				r--;
			}
			if (p < r) {
				swap(arr, p, r);
			}
		}
		return r;
	}
	
	public static int getMedian(int[] arr, int p, int r) {
		int size = r - p + 1;
		int groupSize = (size % 5 == 0) ? (size / 5) : ((size / 5) + 1);
		int indexOfMedians = 0;
		int[] medians = new int[groupSize];
		HashMap<Integer, Integer> mediansOfValueAndIndex = new HashMap<Integer, Integer>();
		for (int i = 0; i < groupSize; i++) {
			if (i == groupSize - 1) {
				insertSort(arr, p + (i * 5), r);
				medians[indexOfMedians++] = arr[(p + (i * 5) + r) >>> 1];
				mediansOfValueAndIndex.put(arr[(p + (i * 5) + r) >>> 1], (p + (i * 5) + r) >>> 1);
			} else {
				insertSort(arr, p + (i * 5), p + (i * 5) + 4);
				medians[indexOfMedians++] = arr[p + (i * 5) + 2];
				mediansOfValueAndIndex.put(arr[p + (i * 5) + 2], p + (i * 5) + 2);
			}
		}
		insertSort(medians, 0, groupSize - 1);
		return mediansOfValueAndIndex.get(medians[(groupSize - 1) >>> 1]);
	}
	
	public static void insertSort(int[] arr, int p, int r) {
		int before_i = 0;
		int value_i = 0;
		for (int i = p + 1; i <= r; i++) {
			before_i = i - 1;
			value_i = arr[i];//不能删，这个是辅助空间来保存arr[i]
			while (before_i > p - 1 && arr[before_i] > value_i) {
				arr[before_i + 1] = arr[before_i--];
			}
			arr[before_i + 1] = value_i;
		}
	}
	
	public static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
}
